# -*- coding: utf-8 -*-

class QuickSort:
	"""
		Algoritmo QuickSort
		Parâmetro de entrada:
			A: Lista a ser ordenada
	"""
	def __init__(self, A):
		self.A = A
		self.sort(0, len(self.A) - 1)

	def sort(self, p, r):
		"""
			Método para ordenar as partições criadas a partir da lista
		"""
		if p < r:
			q = self.partition(p, r)
			self.sort(p, q - 1)
			self.sort(q + 1, r)

	def partition(self, p, r):
		"""
			Método que separa a lista em duas tabelas a partir de um pivot, o pivot neste caso é o ultimo elemento da lista.
			A tabela esquerda tem os valores mais baixos que o pivot, enquanto que a direita tem valores mais altos que o pivot.
		"""
		x = self.A[r]
		i = p - 1
		for k in range(p, r):
			if self.A[k] <= x:
				i += 1
				self.A[i], self.A[k] = self.A[k], self.A[i]
		self.A[i + 1], self.A[r] = self.A[r], self.A[i + 1]
		return (i + 1)